// Package _4__在排序数组中查找元素的第一个和最后一个位置 main
// @Title _4__在排序数组中查找元素的第一个和最后一个位置
// @Description
// @Author  == 琳琳也叫王木木 ==  2022-02-18 15:20
// @Create  2022-02-18 15:20
package main

import (
	"fmt"
)

func searchRange(nums []int, target int) []int {
	if len(nums) == 0 {
		return []int{-1, -1}
	}
	low := lowBound(nums, target)
	upper := upperBound(nums, target) - 1
	if low == len(nums) || nums[low] != target {
		return []int{-1, -1}
	}
	return []int{low, upper}
}

func lowBound(nums []int, target int) int {
	l, r := 0, len(nums)
	var mid int
	for l < r {
		mid = (r-l)>>1 + l
		if nums[mid] >= target {
			r = mid
		} else {
			l = mid + 1
		}
	}
	return l
}

func upperBound(nums []int, target int) int {
	l, r := 0, len(nums)
	var mid int
	for l < r {
		mid = (r-l)>>1 + l
		if nums[mid] > target {
			r = mid
		} else {
			l = mid + 1
		}
	}
	return l
}

func main() {
	fmt.Println(lowBound([]int{5, 7, 7, 8, 8, 8, 8, 10}, 8))
	fmt.Println(upperBound([]int{5, 7, 7, 8, 8, 8, 8, 10}, 8))
	//fmt.Println(searchRange([]int{5,7,7,8,8,8,8,10},8))
}
